#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;


void getMax(stack<int> &myStack, vector<int> &height, int i, int &maxArea)
{
    int top = myStack.top();
    int high = height[top];
    myStack.pop();
    int right = i, left = myStack.empty()? -1 : myStack.top();
    int area = high * (right - left-1);
    if (maxArea < area)
         maxArea = area;
}

        int largestRectangleArea(vector<int> &height) {
            if (height.size() == 0) return 0;
            stack<int> myStack;
            int maxArea =-1 ;
            for (int i = 0; i < height.size(); i++) {
                if (myStack.empty() || height[myStack.top()] <= height[i]) {
                    myStack.push(i);
    				continue;
				}
                while(!myStack.empty() && height[myStack.top()] > height[i])
                    getMax(myStack, height, i, maxArea);
                myStack.push(i);
            }
            while(!myStack.empty())
                    getMax(myStack, height, height.size(), maxArea);

            return maxArea;
        }



class Solution {
    public:
        int maximalRectangle(vector<vector<char> > &matrix) {
            if (matrix.size() == 0) return 0;
            int row = matrix.size();
            int col = matrix[0].size();
            vector<vector<int> > m(row+1, vector<int>(col+1, 0));
            for (int i = 1; i <= row; i++) {
                for (int j = 1; j <= col; j++) {
                   if (matrix[i-1][j-1] == '1') m[i][j] = 1;         
                }
            }

            for (int i = 1; i <= row; i++) {
                for (int j = 1; j <= col; j++) {
                    if (m[i][j] == 1 && m[i-1][j] > 0) {
                        m[i][j] += m[i-1][j];
                    }
                }
            }
            int maxArea = 0;
            for (int i = 1; i <= row; i++) {
                maxArea = max(maxArea, largestRectangleArea(m[i]));
            }
            return maxArea;
        }
};


//add better code
    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.size() == 0) return 0;
        vector<vector<int> > pre(matrix.size()+1, vector<int>(matrix[0].size()+1, 0));
        int ans = 0;
        for (int i = 1; i < pre.size(); i++) {
            for (int j = 1; j < pre[0].size(); j++) {
                if (matrix[i-1][j-1] == '0') pre[i][j] = 0;
                else pre[i][j] = pre[i-1][j] + 1;
            }
        }
        for (int i = 1; i < pre.size(); i++)
            ans = max(ans, largestRectangleArea(pre[i]));
        return ans;

    }

//test in 1337 online judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;

    cout << "-----------------Test 1--------------------" << endl;
    int matrix[][6] = {{0,1,1,1,1,0},
                        {0,1,0,1,0,0},
                        {0,1,1,1,1,0},
                        {0,1,1,1,1,0},
                        {0,1,1,1,1,0},
                        {0,1,1,1,0,0},
                        {0,1,1,1,1,0}};
    vector<vector<char> > input(7, vector<char>(6));
    for(int i = 0; i <7; i++) {
        for (int j = 0; j < 6; j++) {
            if (matrix[i][j] == 0) input[i][j] = '0';
            else input[i][j] = '1';
        }
    }


    int area = mySolution.maximalRectangle(input);
    cout << "Area is " << area << endl;

    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
